package algorithm.heap;

public class MaxHeap {


    private Integer[] data;

    private int capacity;

    private int count;

    public MaxHeap(int capacity) {
        data = new Integer[capacity + 1];
        this.capacity = capacity;
    }


    public MaxHeap(Integer[] data,int capacity){
        this.capacity = capacity+1;
        this.data = new Integer[this.capacity];
        for (int i = 0; i < data.length; i++) {
            this.data[i+1]=data[i];
            count++;
        }
        for (int i = count / 2 ; i >0; i--) {
            shiftDown(i);
        }
    }


    private int getCount() {
        return count;
    }


    public void put(Integer item) {
        if (count >= capacity) {
            throw new RuntimeException("超出容量限制");
        }
        data[++count] = item;
        shiftUp(count);

    }

    private void shiftUp( int index) {
        while (index > 1 && data[index / 2] < data[index]) {
            swap(data, index / 2, index);
            index = index / 2;
        }
    }


    public Integer pop() {
        Integer item = data[1];
        data[1] = data[count--];
        shiftDown(1);
        return item;
    }

    private void shiftDown(int index) {
        while (index*2<=count){
            int j = index*2;
            if (index*2+1<=count&&data[index*2+1]>data[index*2]){
                j++;
            }
            if (data[index]<data[j]){
                swap(data,index,j);
                index=j;
            }else{
                break;
            }
        }
    }


    private void swap(Integer[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.put(1);
        maxHeap.put(2);
        maxHeap.put(3);
        maxHeap.put(4);
        maxHeap.put(5);
        maxHeap.put(7);
        maxHeap.put(8);
        maxHeap.put(9);
        maxHeap.put(19);
        maxHeap.put(22);
        for (int i = 0; i < 10; i++) {
            System.out.println(maxHeap.pop());
        }

    }
}
